package test.n00300;


public class Problem00320 {
    public static void main(String[] args) {
        //println("(()");
        //println(")()())");
        println("()(()");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.longestValidParentheses(s));
    }

    private static class Solution {
        /**
         * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
         * <p>
         * 解题思路:
         * 动态规划
         * “……()” =>     dp[i]=dp[i−2]+2
         * “……))” =>     dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
         *
         * @param s
         * @return
         */
        public int longestValidParentheses(String s) {
            int r = 0;
            int[] dp = new int[s.length()];
            for (int i = 1; i < dp.length; i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    r = Math.max(r, dp[i]);
                }
            }
            return r;
        }
    }
}
